\section{Related Work}
This section discusses different directory designs for CMP. 
Shadow tags duplicate all the tags present in the private cache 
and construct the sharing vector by looking up the tags when
accessed. The design is simple in concept and works well in
current multicores including SUN's Niagara2~\cite{niagara2}. 
The bigger challenge is that it requires an energy-intensive associative 
search to construct the sharing pattern.
We have shown that using the techniques described in this paper 
we can improve space consumption by a factor of 3$\times$ at 64 cores
without the need for associative 
lookup.  


Tagless directory~\cite{zebchuk-micro-2009} uses bloom filters to map
the tags in each cache set. The bloom filters concisely
summarize the tags for each set in every core and completely
eliminates the associative search on lookups.  Overall, it reduces
storage compared to shadow tags by a factor of the number of ways in
the L1 cache.  The benefits of the bloom filters are limited for 
multicores with a large number of cores since the per-bucket
sharing vector becomes a significant area overhead.

% \sys\ optimizes the tagless system and the coherence directory size
% is a function of the number of sets in the L1 and number of unique
% sharing patterns possible in a target application. This enables it to
% achieve significant benefits over tagless for large
% multicores. Tagless grows as a function of the number of
% sets in the L1 and number of cores in the system. 


%Shadow tags are the most basic form of coherence
%directory which grows with L1 cache size (sets and ways) and number
%of cores in the system. 
Directory cache~\cite{tag_dir,acacio_level} limits the size of the
directory by restricting the number of blocks that the directory
holds the sharing information for. With this limitation, if one block is
not present in the directory cache, either all the shared copies have
to be invalidated, or the cache block must be defaulted to shared by
all the processors. Cuckoo directory~\cite{cuckoo-dir} uses an improved
hashing algorithm to eliminate associativity-related tag evictions in
the directory cache. 
Other proposals try to combine a small directory cache with
a larger in-memory directory~\cite{tag_dir,waypoint}. Such designs
essentially emulate a big directory cache, but they require complex
protocol extensions that touch off-chip metadata, and some directory
accesses will suffer long latencies.


Full map directory~\cite{Censier_dir} is a simple solution for CMPs
with an inclusive shared last-level cache. 
The bit vector indicating the sharers is
associated with the cache line at the shared cache. Full map directory
imposes significant storage penalty because the shared cache
is usually much larger (24MB on the latest Itanium~\cite{itanium9300}) and
includes lines that are not cached at lower levels. SPACE~\cite{zhao-pact-2010}
sought to optimize full map by making the observation that many
entries in the shared cache store redundant patterns.  It decouples
the sharing pattern from the directory entries, and only represent
patterns present in the application. Each cache block in the inclusive
cache includes a pointer to the pattern table. Unfortunately, even
uncached blocks include the pointer and this leads to significant
space overhead compared shadow tag-based approaches.



Coarse vectors~\cite{Gupta90reducingmemory,simoni_thesis}, sharer
pointers ~\cite{sgi_origin,limited-pointer-dir}, and segmented
vectors~\cite{Choi99segmentdirectory} all try to
compress the sharing vector using more compact encodings. 
Based on the encoding type, these compressed directories can represent 
only a limited 
number of sharing patterns, and introduce imprecision (hard-coded at 
design time) or extra latency 
for other patterns. 


Overall, \sys\ is agnostic to the type of shared cache (inclusive or exclusive), 
affords significant compression over the previously known best approach, Tagless, and 
loses precision more gracefully based on an application's coherence requirements.
